1. Field of the Invention
The present invention relates to a hierarchially arranged memory system for a data processing system having virtual addressing and which possesses a peripherally assigned auxiliary memory as a background memory and a multi-level working memory with a main memory and a buffer store of low capacity and short access time, and to a method for carrying out storage operations in such a memory system.
2. Description of the Prior Art
The hierarchial organization of several partial memories into a multi-level memory system of great capacity and an advantageous mean access time has been frequently utilized in order to obtain a considerably greater data flow, not only in large computer systems, but also in medium and even smaller data processing systems. Such memory structures are illustrated extensively, with respect to their properties, for example, in "Electronic Computer Set Ups," 1976, Pages 122-128 in an article entitled "Buffer Storage Structures."
The complete programs of the individual processes, which simultaneously flow in the data processing system, are only placed in the lowest storage level--referenced here as the secondary memory--in all hierarchially organized multi-level storage systems. Each partial memory of the hierarchy level contains only portions of these programs. The loading strategies for these storage systems are therefore essential and, to a great extent, determine their properties. The central processor, or also several processors, of the data processing system first addresses the partial memory of the highest hierarchy level in such a memory system. Not until a so-called "miss," i.e. when the searched storage word is not contained at that level, is the next lower hierarchy level accessed.
Inasmuch as a miss can have different consequences in a partial memory, the following should first be defined here. Except for the secondary memory which is to be understood as a background memory, all partial memories of the hierarchy level are referenced as a working memory system in which a miss in a hierarchy level still permits a direct access to the next lower hierarchy level. Only a miss in the total working memory system requires a page change, i.e. fetching a storage page from the secondary memory.
The storage operation "page exchange," however, is very detailed as it often requires first a removal of a storage page, up to now located in the working memory system, in order to provide room for the missing storage page. Due to the time involved in such an operation, such a page exchange simultaneously makes a process alternation necessary, i.e. a detaching of the process presently in operation by a successor process so as not to keep the requesting processor in a stand-by condition and to thus lower the efficiency of the data processing system too much.
These disadvantages of loading strategy of a page exchange upon request lead to the suggestion to again provide each process, as soon as it replaces an inactive process, with its original actual storage area in the working memory system. Presently, this only means to keep the number of pages ready for a process in the main memory at the beginning of a new operating period, this being the number which was required in the preceding processing period for storage pages for which a storage access resulted. This has the advantage that in a process exchange in the working memory system, first sufficient storage page is available, because a storage page--meanwhile overriden--can be directly fetched from the page memory without previously having to remove a storage page from the working memory system.
It has already been suggested, moreover, to directly provide a process, being processed anew, with its actual previous storage area, i.e. to provide it immediately at the beginning of the new processing period with the storage pages previously required in the program flow. This loading strategy considerably decreases the number of page misses causing a page exchange. A miss can only still occur when the actual storage area made available alters its size in a processing period. However, a page, and therefore a process, exchange or alteration based thereupon cannot be completely eliminated.
Now it is not sufficient to only make available its actual storage area in the lowest hierarchy level of the working memory system--often referenced main memory--for an active process. It also often proves expedient, moreover, to keep the actual storage areas of other, presently inactive processes, ready because those storage areas, for example, only wait for the entry of a storage page from the secondary memory, or for the finishing of an input/output operation of a peripheral apparatus of the data processing system.
To this is added, furthermore, that the operating system of the data processing system per se engages a relatively large portion of the capacity of the working memory system as different operating system functions must be kept "storage-resident" because they are frequently called upon for use. In a multi-program operation of data processing systems having virtual addressing, particularly the page alternation and address translation routines with the simplicity of address translation tables, separately kept for each process, which tables are also maintained by the operating system of the data processing system, can be disadvantageous.
Thus, depending upon the development level and number of processes simultaneously to be processed, a working memory capacity of several mega bytes is already required in present data processing systems. The storage capacity required for storage-resident system functions can thereby readily lie in the magnitude of 100 KB. As in each partial memory--in hierarchially arranged storage system--of higher hierarchy level, again and again only takes over a partial area of the next lower hierarchy level, does this mean a main memory capacity in the magnitude of mega bytes.
However, such large main memories are so expensive that one must make an attempt to provide presuppositions so that less expensive storage media can be utilized, such as CCD memories. However, these less expensive storage media--in the present state of technology--have access times which are longer, in general, by one magnitude, which then considerably diminishes the output of the data processing system.